package training.队列栈;

import jdk.internal.org.objectweb.asm.ClassReader;

import java.util.ArrayDeque;
import java.util.Stack;

public class _84柱状图中最大的矩形 {


    public static void main(String[] args) {


        int[] heights = {2, 1, 5, 6, 2, 3};

        System.out.println(largestRectangleArea3(heights));

    }


    private static int largestRectangleArea(int[] heights) {


        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int[] hs = new int[heights.length + 2];

        int max = 0;

        System.arraycopy(heights, 0, hs, 1, heights.length);


        for (int i = 0; i < hs.length; i++) {


            while (!deque.isEmpty() && hs[i] < hs[deque.peek()]) {


                //栈顶的柱子下标
                int curr = deque.pop();

                // 栈顶左边界的柱子
                int area = (i - 1 - deque.peek()) * hs[curr];

                max = Math.max(max, area);
            }

            deque.push(i);
        }


        return max;
    }

    private static int maxAreaFor(int[] heights) {

        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int[] hs = new int[heights.length + 2];

        int max = 0;

        System.arraycopy(heights, 0, hs, 1, heights.length);

        for (int i = 0; i < hs.length; i++) {

            while (!deque.isEmpty() && hs[i] < hs[deque.peek()]) {


                int curr = deque.pop();

                max = Math.max(max, hs[curr] * (i - deque.peek() - 1));

            }


            deque.push(i);

        }

        return max;

    }


    private static int largestRectangleArea3(int[] heights) {

        int max = 0;

        ArrayDeque<Integer> deque = new ArrayDeque<>();

        int[] hs = new int[heights.length + 2];

        System.arraycopy(heights, 0, hs, 1, heights.length);

        for (int i = 0; i < hs.length; i++) {


            //栈顶元素的右边界找到了，以栈顶柱子的面积可以进行计算了
            //有边界是 i ，左边界是 栈顶以下的第一个元素
            while (!deque.isEmpty() && hs[deque.peek()] > hs[i]) {

                int pop = deque.pop();
                int area = (i - pop) * hs[pop];
                max = Math.max(max, area);

            }
            //记录下标
            deque.push(i);
        }

        return max;
    }
}
